home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Heap / Heap.h < prev    next >
Encoding:
Text File  |  1997-06-28  |  1.2 KB  |  58 lines  |  [TEXT/CWIE]
  1. // Heap.h
  2.  
  3. #ifndef Heap_h
  4. #define Heap_h
  5.  
  6. #ifndef Integers_h
  7. #include "Integers.h"
  8. #endif
  9. #ifndef Assert_h
  10. #include "Assert.h"
  11. #endif
  12.  
  13. template < class Element > class HeapLink;
  14.  
  15. template < class Element >
  16. class Heap
  17.   {
  18.     typedef Element ElementType;
  19.     typedef HeapLink< Element > LinkType;
  20.     typedef Heap< Element > HeapType;
  21.     typedef bool (ElementType::*Comparator)( const Element& ) const;
  22.     
  23.     private:
  24.         uint32 nodeCount;
  25.         LinkType *top;
  26.         const Comparator below;
  27.         
  28.         LinkType** SubHeap( uint32 path );
  29.         LinkType& RemoveLast();
  30.         
  31.         void SinkNode( LinkType**& subHeap, LinkType*& newNode );
  32.         void Percolate( LinkType** subHeap );
  33.         
  34.         void Validate( LinkType& node, uint32 level ) const;
  35.         
  36.         // not implemented:
  37.             Heap( const Heap& );
  38.             void operator=( const Heap& );
  39.         
  40.     public:
  41.         Heap( Comparator below );    // Typically operator<=( const Element& ) const
  42.         ~Heap();
  43.         
  44.         Comparator Below() const    { return below; }
  45.         
  46.         bool IsEmpty() const            { return top == 0; }
  47.         
  48.         LinkType& Top() const        { Assert( top != 0 ); return *top; }
  49.         LinkType& Pop();
  50.         
  51.         void Add( LinkType& );
  52.         void Remove( LinkType& );
  53.         
  54.         void Validate() const;         // Checks a set of assertions
  55.   };
  56.  
  57. #endif
  58.